#ifndef LIST_H_
#define LIST_H_
#include <iostream>
using std::cout;
#include "mtm_ex4.h"

/* ####################### List declaration ####################### */

/**
 * A generic list implementation, allows inserting, removing,
 *  finding, sorting and iterating through items in the list.
 * Notes:
 * 	- Class T must implement a default constructor.
 *  - To support list comparison, class T must implement a comparison operator.
 */
template<class T>
class List {
public:
	/**
	 * List's default C'tor, initializes a new list.
	 */
	List();

	/**
	 * List's copy C'tor, this list will be a copy of the given one.
	 * @param list - the list to be copied.
	 */
	List(const List& list);

	/**
	 * Deallocates all items in the lists and the list itself.
	 */
	~List();

	/**
	 * Assignment operator between two lists.
	 * clears the list and copies the given one.
	 *
	 * @param list - the list to be assigned to this list.
	 * @return this list after assignment.
	 */
	List& operator=(const List& list);

	/**
	 * Class Iterator is used to iterate over List<T> elements.
	 * use begin() to get first element, then use operator overloads:
	 * 	" ++ "  - advance iterator (use pre or post).
	 * 	" *  "  - dereference to get actual T& element.
	 * 	" == "  - iterators are equal if they belong to same list and hold the
	 * 			  same element.
	 * 	" != "  - NOT "==".
	 *
	 * 	List ends when end() is reached.
	 * 	Increment "++" and Dereference "*" on list.end() are undefined.
	 */
	class Iterator;

	/**
	 * Class ConstIterator is similar to Class Iterator, but iterates
	 * over const List<T> . no altering actions can be applied to the list.
	 * use begin() to get first element, then use operator overloads:
	 * 	" ++ "  - advance iterator (use pre or post).
	 * 	" *  "  - dereference to get actual const T& element.
	 * 	" == "  - iterators are equal if they belong to same list and hold the
	 * 			  same element.
	 * 	" != "  - NOT "==".
	 *
	 * 	List ends when end() is reached.
	 * 	Increment "++" and Dereference "*" on list.end() are undefined.
	 */
	class ConstIterator;

	/**
	 * @return an iterator to the first element in the list.
	 */
	Iterator begin();

	/**
	 * @return an iterator to the element after the last element in the list.
	 */
	Iterator end();

	/**
	 * @return an iterator to the first element in the constant list.
	 */
	ConstIterator begin() const;

	/**
	 * @return an iterator to the element after the last element in the
	 *   constant list.
	 */
	ConstIterator end() const;

	/**
	 * Insert an element to the end of the list.
	 * Note - the element is copied, not pointed to.
	 * @param item - A reference to an element to add to the list.
	 */
	void insert(const T& item);

	/**
	 * Insert an element to the list, one item before the one pointed by
	 *  the given iterator.
	 * Note - the element is copied, not pointed to.
	 *
	 * @param item - A reference to an element to add to the list.
	 * @param iterator - an iterator holding a position one step after where
	 *  the element should be added.
	 * @exceptions - mtm::NON_MATCHING_LIST - if iterator is not of the same
	 * 	list you wish to add to.
	 */
	void insert(const T& item, const Iterator& iterator);

	/**
	 * Removes the list element positioned at given iterator position.
	 * Note - using the given iterator after calling this function is undefined.
	 * @param iterator -an iterator pointing to the item that should be removed.
	 * @exceptions
	 * 	mtm::NON_MATCHING_LIST - if iterator is not of the same
	 * 	 list you wish to remove from.
	 * 	mtm::ELEMENT_NOT_FOUND - if the list is empty or the iterator points to
	 * 	 the item after the last item in the list.
	 */
	void remove(const Iterator& iterator);

	/**
	 * Finds the first element in the list that meets the requirements of
	 * predicate.
	 * Note - even if several elements exist, the method returns an iterator to
	 * the element closest to list start.
	 *
	 * @param predicate - Function object used for conditional check.
	 * 	should get an item of type T and return a boolean value indicating if
	 * 	it matches the condition.
	 * @return
	 * 		if found - an iterator to the element.
	 * 		Else - an iterator to one item after the end of the list.
	 */
	template<class FindFunc> Iterator find(FindFunc predicate);

	/**
	 * Finds the first element in the list that meets the requirements of
	 * predicate.
	 * Note - even if several elements exist, the method returns an iterator to
	 * the element closest to list start.
	 *
	 * @param predicate - Function object used for conditional check.
	 * 	should get an item of type T and return a boolean value indicating if
	 * 	it matches the condition.
	 * @return
	 * 		if found - a constant iterator to the element.
	 * 		Else - a constant iterator to one item after the end of the list.
	 */
	template<class FindFunc> ConstIterator find(FindFunc predicate) const;

	/**
	 * Sorts the list according to given predicate.
	 *
	 * @param predicate - function object that compares two elements.
	 * 	returns true if first < second and false otherwise.
	 */
	template<class SortFunc> void sort(SortFunc predicate);

	/**
	 * @return Number of elements in the list (0 for empty list).
	 */
	int getSize() const;

private:
	/**
	 * A class representing a node in a linked list of type T.
	 */
	class Node;
	int size;
	Node *first, *last;

	/**
	 * Gets the node before the one pointed by given iterator.
	 * @return a reference to the previous node.
	 */
	Node& getPreviousNode(const Iterator& iterator);

	/**
	 * Clears the items in the list.
	 */
	void clear();
};

/**
 * Compares two lists.
 * Note - Assumes type T has operator "==" overloaded.
 *
 * @return
 * 		 true - if lists are equal in content (element wise).
 * 		 note that (listA == listA)	returns true.
 * 		 false - otherwise.
 */
template<class T> bool operator==(const List<T>& list1, const List<T>& list2);

/**
 * Compares two lists.
 * Note - Assumes type T has operator "==" overloaded.
 *
 * @return
 * 		 true - if lists are not equal in content (element wise).
 * 		 false - if lists are equal.
 */
template<class T> bool operator!=(const List<T>& list1, const List<T>& list2);

/* ####################### Iterator declaration ####################### */

template<class T>
class List<T>::Iterator {
	/**
	 * Creates a new iterator that will point to the given node in
	 * the given list.
	 */
	Iterator(const List<T>* list, Node* node);

	friend class List<T> ;
	const List<T>* list;
	Node* currentNode;

public:
	/**
	 * Increments the iterator to the next element in a list.
	 * @return
	 * 	an iterator to the element after the one the iterator is pointing to.
	 */
	Iterator& operator++();

	/**
	 * Increments the iterator to the next element in a list.
	 * @param int - dummy parameter to distinguish between "++" operators.
	 * @return an iterator to the current element the iterator is pointing to.
	 */
	Iterator operator++(int);

	/**
	 * Dereferences an iterator to get an actual T& object.
	 * @return A reference to the item the iterator is pointing to.
	 * @exceptions
	 * 	mtm::ELEMENT_NOT_FOUND - if the iterator points to one item after
	 * 	 the last item in the list.
	 */
	T& operator*() const;

	/**
	 * Checks if this iterator and given iterator are of the same list and
	 * hold the same element position in the list.
	 *
	 * @param iterator - to be compared with this iterator.
	 * @return
	 * 		true - if iterators are of the same list and position.
	 * 		false - otherwise.
	 */
	bool operator==(const Iterator& iterator) const;

	/**
	 * Checks if this iterator and given iterator are of another list OR
	 * hold another element position in the list.
	 *
	 * @param iterator - to be compared with this iterator.
	 * @return
	 * 		false - if iterators are of the same list and position.
	 * 		true - otherwise.
	 */
	bool operator!=(const Iterator& iterator) const;
};

/* ################### ConstIterator declaration ################### */

template<class T>
class List<T>::ConstIterator {
	/**
	 * Creates a new constant iterator that will point to the given node in
	 * the given list.
	 */
	ConstIterator(const List<T>* list, Node* node);

	friend class List<T> ;
	const List<T>* list;
	Node* currentNode;

public:
	/**
	 * Creates a new constant iterator from the given iterator.
	 * The new constant iterator will point to the same item in the same list
	 * as the given iterator, but will not allow to do changes on the list.
	 * @param iterator - the iterator to copy.
	 */
	ConstIterator(const Iterator& iterator) :
			list(iterator.list), currentNode(iterator.currentNode) {
	}

	/**
	 * Increments the iterator to the next element in a constant list.
	 * @return
	 * 	an iterator to the element after the one the iterator is pointing to.
	 */
	ConstIterator& operator++();

	/**
	 * Increments the iterator to the next element in a constant list.
	 * @param int - dummy parameter to distinguish between "++" operators.
	 * @return an iterator to the current element the iterator is pointing to.
	 */
	ConstIterator operator++(int);

	/**
	 * Dereferences an iterator to get an actual T& object.
	 * @return A constant reference to the item the iterator is pointing to.
	 * @exceptions
	 * 	mtm::ELEMENT_NOT_FOUND - if the iterator points to one item after
	 * 	 the last item in the list.
	 */
	const T& operator*() const;

	/**
	 * Checks if this iterator and given iterator are of the same list and
	 * hold the same element position in the list.
	 *
	 * @param iterator - to be compared with this iterator.
	 * @return
	 * 		true - if iterators are of the same list and position.
	 * 		false - otherwise.
	 */
	bool operator==(const ConstIterator& iterator) const;

	/**
	 * Checks if this iterator and given iterator are of another list OR
	 * hold another element position in the list.
	 *
	 * @param iterator - to be compared with this iterator.
	 * @return
	 * 		false - if iterators are of the same list and position.
	 * 		true - otherwise.
	 */
	bool operator!=(const ConstIterator& iterator) const;
};

/* ####################### Node declaration ####################### */

template<class T>
class List<T>::Node {
public:
	/**
	 * Creates a node with no data (requires a default constructor from type T),
	 * and next node is a null pointer.
	 */
	Node();

	/**
	 * Creates a node with given data and pointer to the given next node.
	 */
	Node(const T data, Node* next);

private:
	T data;
	Node* next;
	friend class List<T> ;
};

/* ####################### List Implementation ####################### */

template<class T>
List<T>::List() :
		size(0), first(new Node), last(first) {
}

template<class T>
List<T>::List(const List<T>& list) :
		size(0), first(new Node), last(first) {
	for (const T& item : list) {
		insert(item);
	}
}

template<class T>
List<T>::~List() {
	clear();
	delete last;
}

template<class T>
List<T>& List<T>::operator=(const List<T>& list) {
	if (&list == this) {
		return *this;
	}

	clear();
	for (const T& item : list) {
		insert(item);
	}

	return *this;
}

template<class T>
bool operator==(const List<T>& list1, const List<T>& list2) {
	bool listsAreEqual = true;

	typename List<T>::ConstIterator iteratorA = list1.begin(), iteratorB =
			list2.begin();
	while (listsAreEqual) {
		if (iteratorA == list1.end() || iteratorB == list2.end()) {
			return iteratorA == list1.end() && iteratorB == list2.end();
		}
		if (*iteratorA == *iteratorB) {
			++iteratorA;
			++iteratorB;
		} else {
			listsAreEqual = false;
		}
	}
	return listsAreEqual;
}

template<class T>
bool operator!=(const List<T>& list1, const List<T>& list2) {
	return !(list1 == list2);
}

template<class T>
typename List<T>::Iterator List<T>::begin() {
	return Iterator(this, first);
}

template<class T>
typename List<T>::Iterator List<T>::end() {
	return Iterator(this, last);
}

template<class T>
typename List<T>::ConstIterator List<T>::begin() const {
	return ConstIterator(this, first);
}

template<class T>
typename List<T>::ConstIterator List<T>::end() const {
	return ConstIterator(this, last);
}

template<class T>
void List<T>::insert(const T& item) {
	insert(item, end());
}

template<class T>
void List<T>::insert(const T& item, const Iterator& iterator) {
	if (iterator.list != this) {
		throw mtm::NON_MATCHING_LIST();
	}

	Node* newNode = new Node(item, iterator.currentNode);

	if (iterator.currentNode == first) {
		first = newNode;
	} else {
		getPreviousNode(iterator).next = newNode;
	}

	size++;
}

template<class T>
void List<T>::remove(const Iterator& iterator) {
	if (iterator.list != this) {
		throw mtm::NON_MATCHING_LIST();
	}
	if (iterator == end()) {
		throw mtm::ELEMENT_NOT_FOUND();
	}

	if (iterator.currentNode == first) {
		first = iterator.currentNode->next;
	} else {
		getPreviousNode(iterator).next = iterator.currentNode->next;
	}

	delete iterator.currentNode;
	size--;
}

template<class T>
template<class FindFunc>
class List<T>::Iterator List<T>::find(FindFunc predicate) {
	for (Iterator i = begin(); i != end(); ++i) {
		if (predicate(*i)) {
			return i;
		}
	}
	return end();
}

template<class T>
template<class FindFunc>
class List<T>::ConstIterator List<T>::find(FindFunc predicate) const {
	for (ConstIterator i = begin(); i != end(); ++i) {
		if (predicate(*i)) {
			return i;
		}
	}
	return end();
}

template<class T>
template<class SortFunc>
void List<T>::sort(SortFunc predicate) {
	const int listSize = getSize();
	// copy to array
	T** listArray = new T*[listSize];
	int i = 0;
	for (const T& item : *this) {
		listArray[i++] = new T(item);
	}
	// bubble sort array
	for (int i = 0; i < listSize - 1; i++) {
		for (int j = 0; j < listSize - 1; j++) {
			if (predicate(*listArray[j + 1], *listArray[j])) {
				T* temp = listArray[j];
				listArray[j] = listArray[j + 1];
				listArray[j + 1] = temp;
			}
		}
	}
	// reconstruct list and destroy array
	clear();
	for (int i = 0; i < listSize; i++) {
		insert(*listArray[i]);
		delete listArray[i];
	}
	delete[] listArray;
}

template<class T>
int List<T>::getSize() const {
	return size;
}

template<class T>
class List<T>::Node& List<T>::getPreviousNode(const Iterator& iterator) {
	Node* previousNode = nullptr;
	for (Iterator i = begin(); i != iterator; ++i) {
		previousNode = i.currentNode;
	}

	return *previousNode;
}

template<class T>
void List<T>::clear() {
	Node* next = nullptr;
	for (Node* current = first; current->next != nullptr; current = next) {
		next = current->next;
		delete current;
	}
	first = last;
	size = 0;
}

/* ####################### Iterator implementation ####################### */

template<class T>
List<T>::Iterator::Iterator(const List<T>* list, Node* node) :
		list(list), currentNode(node) {
}

template<class T>
class List<T>::Iterator& List<T>::Iterator::operator++() {
	currentNode = currentNode ? currentNode->next : nullptr;
	return *this;
}

template<class T>
class List<T>::Iterator List<T>::Iterator::operator++(int) {
	Iterator beforeIncrement(*this);
	++*this;
	return beforeIncrement;
}

template<class T>
T& List<T>::Iterator::operator*() const {
	if (!currentNode->next) {
		throw mtm::ELEMENT_NOT_FOUND();
	}
	return currentNode->data;
}

template<class T>
bool List<T>::Iterator::operator==(const Iterator& iterator) const {
	return list == iterator.list && currentNode == iterator.currentNode;
}

template<class T>
bool List<T>::Iterator::operator!=(const Iterator& iterator) const {
	return !(*this == iterator);
}

/* ################### ConstIterator implementation ################### */

template<class T>
List<T>::ConstIterator::ConstIterator(const List<T>* list, Node* node) :
		list(list), currentNode(node) {
}

template<class T>
class List<T>::ConstIterator& List<T>::ConstIterator::operator++() {
	currentNode = currentNode ? currentNode->next : nullptr;
	return *this;
}

template<class T>
class List<T>::ConstIterator List<T>::ConstIterator::operator++(int) {
	ConstIterator beforeIncrement(*this);
	++*this;
	return beforeIncrement;
}

template<class T>
const T& List<T>::ConstIterator::operator*() const {
	if (!currentNode->next) {
		throw mtm::ELEMENT_NOT_FOUND();
	}
	return currentNode->data;
}

template<class T>
bool List<T>::ConstIterator::operator==(const ConstIterator& iterator) const {
	return list == iterator.list && currentNode == iterator.currentNode;
}

template<class T>
bool List<T>::ConstIterator::operator!=(const ConstIterator& iterator) const {
	return !(*this == iterator);
}

/* ####################### Node implementation ####################### */

template<class T> // TODO data is not initialized
List<T>::Node::Node() :
		data(), next(nullptr) {
}

template<class T>
List<T>::Node::Node(const T data, Node* next) :
		data(data), next(next) {
}

#endif /* LIST_H_ */
